package com.xyhuo.leetcode.december;

import java.util.*;

/**
 * 组合总和Ⅱ
 * https://leetcode.cn/problems/combination-sum-ii/
 *
 * @desc 看的题解，折磨得我欲仙欲死
 * @time 2023/12/13
 */
public class CombinationSum2 {

//    public static void main(String[] args) {
//        CombinationSum2 cs2 = new CombinationSum2();
//        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
//        List<List<Integer>> lists = cs2.combinationSum2(candidates, 8);
////        int[] candidates = {5, 2, 1, 2};
////        List<List<Integer>> lists = cs2.combinationSum2(candidates, 5);
////        int[] candidates = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
////        List<List<Integer>> lists = cs2.combinationSum2(candidates, 30);
////        int[] candidates = {1};
////        List<List<Integer>> lists = cs2.combinationSum2(candidates, 1);
//        for (List<Integer> list : lists) {
//            for (Integer integer : list) {
//                System.out.print(integer + " ");
//            }
//            System.out.println();
//        }
//    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, 0);
        return ans;
    }

    private List<Integer> sequence = new ArrayList<>();

    private List<List<Integer>> ans = new ArrayList<>();

    private Set<String> exist = new HashSet<>();

    private void dfs(int[] candidates, int target, int index) {
        if (target == 0) {
            List<Integer> tmp = new ArrayList<>(sequence);

            String str = listStr(tmp);
            if (!exist.contains(str)) {
                ans.add(tmp);
                exist.add(str);
            }
            return;
        }
        if (index < candidates.length && candidates[index] <= target) {
            for (int i = index; i < candidates.length; i++) {
                if (target - candidates[i] < 0) {
                    break;
                }
                if (i > index && candidates[i] == candidates[i - 1]) {
                    continue;
                }
                sequence.add(candidates[i]);
                dfs(candidates, target - candidates[i], i + 1);
                sequence.remove(sequence.size() - 1);
            }
        }
    }

    private String listStr(List<Integer> list) {
        StringBuilder sb = new StringBuilder();
        for (Integer num : list) {
            sb.append(num);
            sb.append("#");
        }
        return sb.toString();
    }

}
